//问题描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 
//习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

//解题思路：
//由于任何丑数都只包含因子2、3、5,因此丑数可表示为(2*x)*(3*y)*(5*z)的形式
//利用动态规划的思想，依次增大x、y、z,并在此过程中保证丑数是逐渐增大的

int GetUglyNumber_Solution(int index) {
    if(index<=0)
        return -1;
    if(index==1)
        return 1;
    vector<int> res(index);
    res[0]=1;
    int kt2=0,kt3=0,kt5=0;
    for(int i=1;i<N;++i)
    {
        res[i]=min(2*res[kt2],min(3*res[kt3],5*res[kt5]));
        if(res[i] == 2*res[kt2]) ++kt2;
        if(res[i] == 3*res[kt3]) ++kt3;
        if(res[i] == 5*res[kt5]) ++kt5;
    }
    return res[index-1];
}